package acwing._1_1AlgorithmBasic;

/**
 * @Project : ProgrammingExercises
 * @Package : ACWing.AlgorithmTemplate
 * @File : _1_2BSearch.java
 * @Author : WangRuoyu
 * @Date 2023/3/9 17:16
 */

public class _1_2BSearch {
    // 整数二分的两个模板，分别判断左侧条件和右侧条件,先写check函数。
    static boolean check(int x) {
        return true;
    }

    static int bSearchint_1(int l, int r) { // 右侧判断，r = mid，mid = (l + r) / 2
        int mid;
        while (l < r) {
            mid = (l + r) / 2;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    static int bSearchint_2(int l, int r) {// 左侧判断，l = mid，mid = (l + r + 1) / 2
        int mid;
        while (l < r) {
            mid = (l + r + 1) / 2;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    // 浮点数二分，例题：求平方根。x>=1
    static double bSearchfloat(double x) {
        double mid;
        double l = 0;
        double r = x;

        while (r - l > 1e-6) {
            mid = (l + r) / 2;
            if (mid * mid >= x) {
                r = mid;
            } else {
                l = mid;
            }
        }

        return l;
    }
}

